1481C - Fence Painting - CodeForces Solution

brute force constructive algorithms greedy *1600

Please click on ads to support us..

Python Code: 

from sys import stdin, stdout
def get_ints(): return map(int, stdin.readline().split())
def PRINT(s): stdout.write(s + '\n')


def logic(n,m,A,B,C):
    differences = [[] for i in range(n)]
    for i in range(n):
        x = B[i]
        if A[i] != x:
            differences[x-1].append(i)
    
    last = C[-1]
    if differences[last-1] != []:
        throw = differences[last-1].pop()
    else:
        throw = -1
        for i in range(n):
            if A[i] == B[i]== last:
                throw = i
                break
        if throw == -1:
            return 'NO'
    C.pop()
    ret = []
    for c in C:
        try:
            ret.append(differences[c-1].pop()+1)
        except:
            ret.append(throw+1)
    for a in differences:
        if a != []:
            return 'NO'

    ret.append(throw+1)
    return 'YES\n' + ' '.join([str(x) for x in ret])

    

for w in range(int(stdin.readline())):
    n,m = get_ints()
    A = [int(x) for x in stdin.readline().split()]
    B = [int(x) for x in stdin.readline().split()]
    C = [int(x) for x in stdin.readline().split()]
    PRINT(logic(n,m,A,B,C))

C++ Code: 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

void work()
{
    int n, m;
    scanf("%d%d", &n, &m);
    
    vector<int> a(n + 1), b(n + 1), c(m + 1), res(m + 1);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &c[i]);
    
    vector<int> mod[n + 1], st(n + 1);
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        st[b[i]] = true;
        if(a[i] != b[i])
        {
            mod[b[i]].push_back(i);
            cnt++;
        }
    }
    
    if(!st[c[m]])
    {
        puts("NO");
        return;
    }
    
    for(int i = m; i >= 1; i--)
        if(mod[c[i]].size())
        {
            int x = mod[c[i]].back();
            mod[c[i]].pop_back();
            res[i] = x;
            cnt--;
        }
    
    if(cnt)
    {
        puts("NO");
        return;
    }
    
    if(!res[m])
    {
        for(int i = 1; i <= n; i++)
            if(b[i] == c[m])
            {
                res[m] = i;
                break;
            }
    }
    
    for(int i = m - 1; i >= 1; i--)
        if(!res[i])
            res[i] = res[i + 1];
    
    puts("YES");
    for(int i = 1; i <= m; i++) printf("%d ", res[i]);
    puts("");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) work();
    return 0;
}


Comments

Submit
0 Comments
More Questions

41C - Email address
1373D - Maximum Sum on Even Positions
1574C - Slay the Dragon
621A - Wet Shark and Odd and Even
1395A - Boboniu Likes to Color Balls
1637C - Andrew and Stones
1334B - Middle Class
260C - Balls and Boxes
1554A - Cherry
11B - Jumping Jack
716A - Crazy Computer
644A - Parliament of Berland
1657C - Bracket Sequence Deletion
1657B - XY Sequence
1009A - Game Shopping
1657A - Integer Moves
230B - T-primes
630A - Again Twenty Five
1234D - Distinct Characters Queries
1183A - Nearest Interesting Number
1009E - Intercity Travelling
1637B - MEX and Array
224A - Parallelepiped
964A - Splits
1615A - Closing The Gap
4C - Registration System
1321A - Contest for Robots
1451A - Subtract or Divide
1B - Spreadsheet
1177A - Digits Sequence (Easy Edition)